#include<vector>
#include<list>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<string>
#include<stack>
using namespace std;



class HuffmanTreeNode
{
public:
    int weight;
    char Sign;
    HuffmanTreeNode(int weight,char Sign)
    {
        this->weight = weight;
        this->Sign = Sign;
        zero = nullptr;
        one = nullptr;
    }
    HuffmanTreeNode *zero;
    HuffmanTreeNode *one;
    
};

class HuffmanTree
{
public:
    HuffmanTreeNode *root;
    vector<HuffmanTreeNode *> *listForDelete;
   
    void InsertHuffmanTreeNode(string address);
    
    void SearchAll();
    void PreOrderSearch(HuffmanTreeNode * node);
    void MidOrderSearch(HuffmanTreeNode *node);
    string Encode(char);
    string EncodeAll(string);
    string Decode(string);
    HuffmanTree(/* args */);
    ~HuffmanTree();
};

bool MyCompareFunction(HuffmanTreeNode * Node1,HuffmanTreeNode * Node2)    
{
    return Node1->weight < Node2->weight;
}

HuffmanTree::HuffmanTree(/* args */)
{
    listForDelete = new vector<HuffmanTreeNode *>;
    root = nullptr;
   
}

HuffmanTree::~HuffmanTree()
{
    vector<HuffmanTreeNode *>::iterator it;
    for (it = listForDelete->begin(); it != listForDelete->end();it++)
    {
        HuffmanTreeNode *deleteNode;
        delete deleteNode;
    }
    delete listForDelete;
}
void HuffmanTree::PreOrderSearch(HuffmanTreeNode * node)
{
    if(!node)
    {
        cout << "/" << " ";
        return;
    }

    cout << node->Sign << " ";
    PreOrderSearch(node->zero);
    PreOrderSearch(node->one);

}
void HuffmanTree::MidOrderSearch(HuffmanTreeNode * node)
{
    if(!node)
        return;
    MidOrderSearch(node->zero);
    cout << node->Sign << " ";
    MidOrderSearch(node->one);
}
void HuffmanTree::SearchAll()
{
    cout << "前序遍历：";
    PreOrderSearch(root);
    cout << endl;
    cout << "中序遍历：";
    MidOrderSearch(root);
    cout << endl;
}
//哈夫曼树的初始化
void HuffmanTree::InsertHuffmanTreeNode(string address)
{
    vector<HuffmanTreeNode *> *Treelist = new vector<HuffmanTreeNode *>;
    string CodeArray;
    fstream file;
    file.open(address);
    CodeArray = address;
    int iSize = CodeArray.size();
    cout << "中间有两个循环" << endl;
    for (int i = 0; i < iSize; i++)
    {
        
        bool FLAG = false;
        vector<HuffmanTreeNode *>::iterator it;
        for (it = Treelist->begin(); it != Treelist->end();it++)
        {
            HuffmanTreeNode *tempNode = *it;
            if(tempNode->Sign==CodeArray[i])
            {
                tempNode->weight++;
                FLAG = true;
                break;
            }
        }
        if(!FLAG)
        {
            HuffmanTreeNode *huffmanNode = new HuffmanTreeNode(1,CodeArray[i]);
            Treelist->push_back(huffmanNode);
            listForDelete->push_back(huffmanNode);
        }
    }
    
        while (Treelist->size() != 1)
        {
            sort(Treelist->begin(), Treelist->end(), MyCompareFunction);
            // cout << "Treelist的大小为" << Treelist->size() << endl;
            vector<HuffmanTreeNode *>::iterator it;
            //cout << "Vector中的情况进行分析" << endl;
            for (it = Treelist->begin(); it != Treelist->end(); it++)
            {
                HuffmanTreeNode *tempNode = *it;
                cout << tempNode->Sign << ":" << tempNode->weight << "  ";
            }
            cout << endl;
            HuffmanTreeNode *smallest_1 = Treelist->at(0);
            HuffmanTreeNode *smallest_2 = Treelist->at(1);
            //cout << "smallest_1:" << smallest_1->Sign << ":" << smallest_1->weight << endl;
            //cout << "smallest_2:" << smallest_2->Sign << ":" << smallest_2->weight << endl;

            Treelist->erase(Treelist->begin(), Treelist->begin() + 2);
            //cout << "你是否减少了呢？" << Treelist->size() << endl;
            HuffmanTreeNode *newTreeNode = new HuffmanTreeNode(
                smallest_1->weight + smallest_1->weight, '#');
            newTreeNode->zero = smallest_1;
            newTreeNode->one = smallest_2;
            Treelist->push_back(newTreeNode);
            listForDelete->push_back(newTreeNode);
        
    }
    root = Treelist->front();
    
    delete Treelist;
    
}

string HuffmanTree::Encode(char a)
{
    
    string outputString = "";
    stack<HuffmanTreeNode *> stackForSearch;
    stack<char> stackForCode;
    bool FLAG = false;
    HuffmanTreeNode *node = root;
    HuffmanTreeNode *prev = root;
    while (node != NULL || !stackForSearch.empty())
    {
        while(node!=NULL)
        {
            stackForSearch.push(node);
            stackForCode.push('0');
            node = node->zero;
        }
        
        node = stackForSearch.top();
        if(!FLAG)
        {
            stackForCode.pop();
            
        }
        FLAG = false;
        if (node->zero == NULL || node->one == prev)
        {
            //cout << node->Sign << endl;
            //cout << "stackForCodeSize:" << stackForCode.size() << endl;
            if (node->Sign == a)
            {
                //cout << "宁到这一步了吗1" << endl;
                //cout << "stackForCodeSize:" << stackForCode.size() << endl;
                while (!stackForCode.empty())
                {
                    //cout << "宁到这一步了吗2" << endl;
                    outputString += stackForCode.top();
                    stackForCode.pop();
                }
                reverse(outputString.begin(),outputString.end());
                return outputString;
            }
            stackForSearch.pop();
            stackForCode.pop();
            prev = node;
            node = NULL;
            FLAG = true;
        }
        else
        {
            node = node->one;
            stackForCode.push('1');
        }
         
    }
    cout << endl;
    return "";
}
string HuffmanTree::EncodeAll(string CodeString)
{
    string outputString = "";
    for (int i = 0; i < CodeString.size(); i++)
    {
        outputString += Encode(CodeString[i]);
    }
    return outputString;
}
string HuffmanTree::Decode(string BinaryCode)
{
    string outputString = "";
    HuffmanTreeNode *node = root;
    for (int i = 0; i < BinaryCode.size(); i++)
    {
        if(BinaryCode[i]=='0')
        {
            node = node->zero;
            if(node->Sign!='#')
            {
                outputString += node->Sign;
                node = root;
            }
        }
        else
        {
            node = node->one;
            if(node->Sign!='#')
            {
                outputString += node->Sign;
                node = root;
            }
        }
    }
    return outputString;
}
int main()
{
    HuffmanTree *huffmantree = new HuffmanTree;
    fstream file;
    file.open("HuffmanTree.txt");
    string address;
    file >> address;
    cout << "第一步" << endl;
    huffmantree->InsertHuffmanTreeNode(address);
    cout << "第二步" << endl;
    huffmantree->SearchAll();
    cout << huffmantree->Encode('c') << endl;
    cout << huffmantree->Encode('f') << endl;
    cout << huffmantree->Encode('a') << endl;
    cout << "输入源码" << endl;
    cout << address << endl;
    cout << "输出编译码" << endl;
    cout << huffmantree->EncodeAll(address) << endl;
    cout << "输出最后的解码" << endl;
    cout << huffmantree->Decode(huffmantree->EncodeAll(address)) << endl;
    file.close();
    return 0;
}